char pairs(char b) {
    if (b == '}') return '{';
    if (b == ']') return '[';
    if (b == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], t = 0;
    for (int k = 0; k < n; k++) {
        char ch = pairs(s[k]);
        if (ch) {
            if (t == 0 || stk[t - 1] != ch) {
                return false;
            }
            t--;
        } else {
            stk[t++] = s[k];
        }
    }
    return t == 0;
}